﻿#include <iostream>

//int main()
//{
//	int a = 10;
//	int b = 10;
//	const int& ra = a;
//
//	const int* pa = &a;
//	pa = &b;
//	*pa = 100;
//
//	int c = 10;
//	int d = 10;
//	int* const pc = &c;
//	pc = &d;
//}

// ----------------------------------------------------------------------------------------------

void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int temp = arr[i + 1];
		int end = i;
		while (end>=0)
		{
			if (arr[end] > temp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = temp;
	}
}

void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int temp = arr[i + gap];
			int end = i;
			while (end >= 0)
			{
				if (arr[end] > temp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = temp;
		}
	}
}

int main()
{
	int arr1[5] = { 1,2,3,4,5 };
	int arr2[5] = { 5,4,3,2,1 };
	int arr3[5] = { 1,1,2,1,1 };

	//选择排序
	//InsertSort(arr1, 5);
	//InsertSort(arr2, 5);
	//InsertSort(arr3, 5);
	//希尔排序
	ShellSort(arr1, 5);
	ShellSort(arr2, 5);
	ShellSort(arr3, 5);
	for (int i = 0; i < 5; i++)
	{
		printf("%d ", arr1[i]);
	}
	printf("\n");
	for (int i = 0; i < 5; i++)
	{
		printf("%d ", arr2[i]);
	}
	printf("\n");
	for (int i = 0; i < 5; i++)
	{
		printf("%d ", arr3[i]);
	}
	printf("\n");
	return 0;
}